Stochastic Process

The distribution "evolves" over time. Put all time onto one line.

Definition

An indexed collection of random variables. A sequence of random variables. $\{ X_i \}$ or $\{ X(t) \}$.

• Each time point (index) ⇒ A random variable in the collection. Each time point (index) ⇒ A distribution.
• The specific value at a time point is random, conforming to the random variable at the time.

Explanation

• $X$: The state of a deck of card. $|\mathcal{X}| = 52!$ possible states(values).
• $\underline{X}$: Fixed Dimension. The state of two decks of card.
• $\{X_i\}$: Open dimension. The state of a deck of card over shuffling.
• $\{\underline{X}_i\}$: Open dimension. The state of two decks of card over shuffling.

Notation

• $X^n = \left( X_1, \ldots, X_n \right)$: A way to represent so as to write the pmf function as $p_{X^n}(x^n)$ of $\{ X_i \}$.
• $\mathcal{X}^{n}$: All possible states, taking into account of all time.
• $x^n \in \mathcal{X}^n$: One possible instance, taking into account of all time.

Example: Card Shuffling

Random variable $X$ represents the state of a card.

$$ \begin{aligned} H(X) &= \log 52! = \sum_{i=1}^{52} \log(i) \approx 226 \text{(bits)} \end{aligned} $$

Stochastic process $\{X_1, \ldots, X_n\}$ represents the shuffling.

One-At-A-Time Shuffling

Each time we select a card uniformly at random from one of the 52 locations and placed it on the top. Then there are 52 different circumstances. $$ \begin{aligned} H(X_{n+1} | X_n, \ldots, X_1) &= H(X_{n+1} | X_n) = \log 52 \approx 5.7 \text{(bits)} \end{aligned} $$ This is a Markov Chain.

by Jon